package cn.edu.thu.thss.algorithm.structures;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉搜索树的实现类。二叉搜索树即为一棵满足如下性质的二叉树：
 * <p>1. 根结点的左右子树均为二叉搜索树
 * <p>2. 根结点至多有两个孩子结点，且左孩子结点的键值<根结点键值<右孩子结点的键值
 * <p>这种数据结构不能保证最高效地执行查找、插入等基本操作，因为它是<b>不平衡</b>的
 * @author EricPai
 */
public class BinarySearchTree<K extends Comparable<K>, V> implements ISearchTree<K, V> {

	private TreeNode<K, V> root;
	private int nodesNum;
	
	/**
	 * 新建一棵没有任何结点的空的二叉搜索树
	 */
	public BinarySearchTree() {
		this(null);
	}
	
	/**
	 * 新建一棵以root为根结点的二叉搜索树
	 * @param root 根结点
	 */
	public BinarySearchTree(TreeNode<K, V> root) {
		insert(root);
	}
	
	public TreeNode<K, V> search(K key) {
		TreeNode<K, V> current = root;
		while (current != null) {
			//如果current的键值比key大，则搜索左子树
			if (current.getKey().compareTo(key) > 0) {
				current = getLeftChild(current);
			} else if (current.getKey().compareTo(key) < 0) { //如果current的键值比key小，则搜索右子树
				current = getRightChild(current);
			} else {
				//相等则直接结束查找
				break;
			}
		}
		return current;
	}


	public TreeNode<K, V> getRoot() {
		return root;
	}

	public int getHeight() {
		int height = 0;
		if (root != null) {
			HashMap<K, Integer> depthMap = new HashMap<K, Integer>();
			depthMap.put(root.getKey(), 1);
			Queue<TreeNode<K, V>> queue = new LinkedList<TreeNode<K, V>>();
			queue.add(root);
			while (!queue.isEmpty()) {
				TreeNode<K, V> temp = queue.poll();
				TreeNode<K, V> child = getLeftChild(temp);
				int curDepth = depthMap.get(temp.getKey());
				if (child != null) {
					queue.add(child);
					depthMap.put(child.getKey(), curDepth + 1);
				}
				child = getRightChild(temp);
				if (child != null) {
					queue.add(child);
					depthMap.put(child.getKey(), curDepth + 1);
				}
				height = Math.max(height, curDepth);
			}
		}
		return height;
	}

	public int getNodesNum() {
		return nodesNum;
	}
	
	/**
	 * 在<code>O(h)</code>时间内返回最小键值结点
	 */
	public TreeNode<K, V> minimum() {
		TreeNode<K, V> current = root;
		//一直沿着左子树查找
		if (current != null) {
			TreeNode<K, V> leftNode = getLeftChild(current);
			while (leftNode != null) {
				current = leftNode;
				leftNode = getLeftChild(current);
			}
		}
		return current;
	}

	/**
	 * 在<code>O(h)</code>时间内返回最大键值结点
	 */
	public TreeNode<K, V> maximum() {
		TreeNode<K, V> current = root;
		//一直沿着右子树查找
		if (current != null) {
			TreeNode<K, V> leftNode = getRightChild(current);
			while (leftNode != null) {
				current = leftNode;
				leftNode = getRightChild(current);
			}
		}
		return current;
	}

	public TreeNode<K, V> tranvseSuccessor(K key) {
		TreeNode<K, V> current = root;
		TreeNode<K, V> previous = null;
		while (current != null) {
			//如果current的键值比key大，则搜索左子树
			if (current.getKey().compareTo(key) > 0) {
				if (previous == null || current.getKey().compareTo(previous.getKey()) < 0) {
					previous = current;
				}
				current = getLeftChild(current);
			} else { //如果current的键值不比key大，则搜索右子树
				current = getRightChild(current);	
			}
		}
		return previous;
	}

	public TreeNode<K, V> tranvsePredecessor(K key) {
		TreeNode<K, V> current = root;
		TreeNode<K, V> previous = null;
		while (current != null) {
			//如果current的键值比key小，则搜索右子树
			if (current.getKey().compareTo(key) < 0) {
				if (previous == null || current.getKey().compareTo(previous.getKey()) > 0) {
					previous = current;
				}
				current = getRightChild(current);
			} else { //如果current的键值不比key大，则搜索右子树
				current = getLeftChild(current);	
			}
		}
		return previous;
	}

	public boolean insert(TreeNode<K, V> node) {
		boolean result = true;
		if (node == null) {
			result = false;
		} else if (root == null) {
			root = node;
		} else {
			TreeNode<K, V> current = root;
			TreeNode<K, V> previous = null;
			while (result && current != null) {
				previous = current;
				if (current.getKey().compareTo(node.getKey()) > 0) {
					current = getLeftChild(current);
				} else if (current.getKey().compareTo(node.getKey()) < 0) {
					current = getRightChild(current);
				} else {
					//此时存在重复键值结点，因此插入失败
					result = false;
				}
			}
			if (result) {
				previous.getChildren().add(node);
				node.setParent(previous);
				nodesNum++;
			}
		}
		
		return result;
	}

	public boolean delete(K key) {
		TreeNode<K, V> toDelNode = search(key);
		if (toDelNode != null) {
			//无论何种情况，删除数据操作都可以归结为小于两个子结点情况
			//有两个子结点时，一定会有后继，且该后继一定最多只有一个子结点，因此删除做法为先删除该后继，然后将该后继的键值和卫星数据拷贝到当前节点内
			TreeNode<K, V> realDelNode = toDelNode.getChildren().size() == 2 ? tranvseSuccessor(key) : toDelNode;
			if (realDelNode.getParent() != null) {
				realDelNode.getParent().getChildren().remove(realDelNode);
				if (realDelNode.getChildren().size() == 1) {
					realDelNode.getChildren().get(0).setParent(realDelNode.getParent());
					realDelNode.getParent().getChildren().add(realDelNode.getChildren().get(0));
				}
			} else {
				root = realDelNode.getChildren().size() == 0 ? null : realDelNode.getChildren().get(1);
			}
			if (toDelNode.getKey() != realDelNode.getKey()) {
				toDelNode.setKey(realDelNode.getKey());
				toDelNode.setValue(realDelNode.getValue());
			}
		}
		return toDelNode != null;
	}

	public List<TreeNode<K, V>> rootFirstTranverse() {
		List<TreeNode<K, V>> resultList = new ArrayList<TreeNode<K, V>>();
		Queue<TreeNode<K, V>> queue = new LinkedList<TreeNode<K, V>>();
		if (root != null) {
			queue.add(root);
		}
		while (queue.size() > 0) {
			TreeNode<K, V> temp = queue.poll();
			resultList.add(temp);
			TreeNode<K, V> child = getLeftChild(temp);
			if (child != null) {
				queue.add(child);
			}
			child = getRightChild(temp);
			if (child != null) {
				queue.add(child);
			}
		}
		return resultList;
	}

	public List<TreeNode<K, V>> descTranverse() {
		List<TreeNode<K, V>> resultList = new ArrayList<TreeNode<K, V>>();
		Stack<TreeNode<K, V>> stack = new Stack<TreeNode<K, V>>();
		if (root != null) {
			stack.add(root);
		}
		//因为为递减顺序输出，所以遍历顺序为右->中->左
		while (!stack.isEmpty()) {
			TreeNode<K, V> tmp = stack.pop();
			while (getRightChild(tmp) != null) {
				stack.push(tmp);
				tmp = getRightChild(tmp);
			}
			resultList.add(tmp);
			while (!stack.isEmpty() && getLeftChild(tmp) == null) {
				tmp = stack.pop();
				resultList.add(tmp);
			}
			TreeNode<K, V> tmpLeft = getLeftChild(tmp);
			if (tmpLeft != null) {
				stack.push(tmpLeft);
			}	
		}
		return resultList;
	}

	public List<TreeNode<K, V>> asceTranverse() {
		List<TreeNode<K, V>> resultList = new ArrayList<TreeNode<K, V>>();
		Stack<TreeNode<K, V>> stack = new Stack<TreeNode<K, V>>();
		if (root != null) {
			stack.add(root);
		}
		//因为为递减顺序输出，所以遍历顺序为左->中->右
		while (!stack.isEmpty()) {
			TreeNode<K, V> tmp = stack.pop();
			while (getLeftChild(tmp) != null) {
				stack.push(tmp);
				tmp = getLeftChild(tmp);
			}
			resultList.add(tmp);
			while (!stack.isEmpty() && getRightChild(tmp) == null) {
				tmp = stack.pop();
				resultList.add(tmp);
			}
			TreeNode<K, V> tmpRight = getRightChild(tmp);
			if (tmpRight != null) {
				stack.push(tmpRight);
			}	
		}
		return resultList;
	}

	/**
	 * 辅助方法，得到树结点的左孩子结点。因为结点个数不会超过2，所以可以认为是在常数时间内完成
	 * @param parent 要查找的结点
	 * @return 该parent结点的左孩子结点，不存在时返回<code>null</code>
	 */
	private TreeNode<K, V> getLeftChild(TreeNode<K, V> parent) {
		TreeNode<K, V> result = null;
		if (parent != null) {
			for (TreeNode<K, V> node : parent.getChildren()) {
				if (node.getKey().compareTo(parent.getKey()) < 0) {
					result = node;
					break;
				}
			}
		}
		return result;
	}
	
	/**
	 * 辅助方法，得到树结点的右孩子结点。因为结点个数不会超过2，所以可以认为是在常数时间内完成
	 * @param parent 要查找的结点
	 * @return 该parent结点的右孩子结点，不存在时返回<code>null</code>
	 */
	private TreeNode<K, V> getRightChild(TreeNode<K, V> parent) {
		TreeNode<K, V> result = null;
		if (parent != null) {
			for (TreeNode<K, V> node : parent.getChildren()) {
				if (node.getKey().compareTo(parent.getKey()) > 0) {
					result = node;
					break;
				}
			}
		}
		return result;
	}
}
